<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>哈希表的封装</title>
</head>
<body>
<script>
  function HashTable() {
    this.storage = []
    this.count = 0
    this.limit = 7

    HashTable.prototype.hashFunc = function (str, size) {
      let hashCode = 0;
      for (let i = 0; i < str.length; i++) {
        hashCode = 37 * hashCode + str.charCodeAt(i)
      }
      return hashCode % size
    }

    // 1. 插入和修改
    HashTable.prototype.put = function (key, value) {
      // 1. 根据key获取对应的index
      let index = this.hashFunc(key, this.limit)

      // 2. 根据index取出对应的bucket
      let bucket = this.storage[index];

      //  3. 判断该bucket是否为null
      if (bucket == null) {
        bucket = []
        this.storage[index] = bucket
      }

      for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i]
        if (tuple[0] === key) {
          tuple[1] = value
          return
        }
      }

      bucket.push([key, value])
      this.count++

      if (this.count > this.limit * 0.75) {
        let newSize = this.limit * 2;
        let newPrime = this.getPrime(newSize)
        this.resize(newPrime)
      }
    }

    HashTable.prototype.get = function (key) {
      let index = this.hashFunc(key, this.limit);
      let bucket = this.storage[index];
      if (bucket == null) {
        return null
      }
      for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i]
        if (tuple[0] === key) {
          return tuple[1]
        }
      }
      return null
    }

    HashTable.prototype.remove = function (key) {
      let index = this.hashFunc(key, this.limit);
      let bucket = this.storage[index];
      if (bucket == null) {
        return null
      }
      for (let i = 0; i < bucket.length; i++) {
        let tuple = bucket[i]
        if (tuple[0] === key) {
          bucket.splice(i, 1)
          this.count--

          if (this.limit > 7 && this.count < this.limit * 0.25) {
            let newSize = Math.floor(this.limit / 2);
            let newPrime = this.getPrime(newSize)
            this.resize(newPrime)
          }

          return tuple[1]
        }
      }
      return null
    }

    HashTable.prototype.isEmpty = function () {
      return this.count === 0
    }

    HashTable.prototype.size = function () {
      return this.count
    }

    HashTable.prototype.resize = function (newLimit) {
      let oldStorage = this.storage

      this.storage = []
      this.count = 0
      this.limit = newLimit

      for (let i = 0; i < oldStorage.length; i++) {
        let bucket = oldStorage[i]
        if (bucket == null) {
          continue
        }
        for (let j = 0; j < bucket.length; j++) {
          let tuple = bucket[j]
          this.put(tuple[0], tuple[1])
        }
      }
    }

    HashTable.prototype.isPrime = function(num) {
      let tmp = Math.ceil(Math.sqrt(num))

      for (let i = 2; i < tmp; i++) {
        if (num % i === 0) {
          return false
        }
      }
      return true
    }

    HashTable.prototype.getPrime = function (num) {
      while (!this.isPrime(num)) {
        num++
      }
      return num
    }
  }

  let ht = new HashTable();
  ht.put("age", 18);
  ht.put("name", "张三");
  ht.put("sex", "男")

  ht.put("name", "李四");
  ht.remove("name")

  // alert(ht.get("name"))
  alert(ht.getPrime(15))


</script>
</body>
</html>